class SolutionZsh {
    public int climbStairs(int n) {
        int[] cache = new int[]{1 , 2};
        if (n <= 2) return cache[n - 1];
        for (int i = 2; i <= n / 2; i++) {
            cache[0] += cache[1];
            cache[1] += cache[0];
        }

        return (n & 1) == 1 ? cache[1] + cache[0] : cache[1];
    }
}